ARC097 D - Equals

提出

code: python

n, m = map(int, input().split())

p = list(map(int, input().split()))

# UnionFindをどう使うか

解答

code: python

n, m = map(int, input().split())

p = list(map(int, input().split()))

class UnionFind:

def __init__(self, n):

def root(self, x):

return x

else:

def union(self, x, y):

x = self.root(x)

y = self.root(y)

if x == y:

return

else:

def same(self, x, y):

return self.root(x) == self.root(y)

uf = UnionFind(n + 1)

# 入れ替え可能ならば同じ集合に属している

# 同じ集合に属する数字は、たとえ直接は入れ替えできなくとも、その中で好きなように並べなおすことが可能

for x, y in xy:

uf.union(x, y)

ans = 0

# 例えば idx=1 を考えると 1 が属する集合と、p1=5 が属する集合が同じであれば、5 を p5 の位置に持ってくることが可能

for idx, v in enumerate(p):

if uf.same(idx + 1, v):

ans += 1

print(ans)

テーマ

メモ